#include <stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
typedef int  QDataType;
typedef struct QueueNode
{
    QDataType data;
    struct QueueNode* next;
}QueueNode;
typedef struct Queue
{
    QueueNode* patil;
    QueueNode* head;
    int size;
}Queue;

void QueueInit(Queue* pq)
{
    assert(pq);
    pq->patil = pq->head = NULL;
    pq->size = 0;
}
void  QueuePush(Queue* pq, QDataType x)
{
    QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
    if (newnode == NULL)
    {
        perror("malloc fail");
        exit(1);
    }
    newnode->data = x;
    newnode->next = NULL;
    if (pq->patil == NULL)
    {
        pq->patil = pq->head = newnode;
    }
    else
    {
        pq->patil->next = newnode;
        pq->patil = pq->patil->next;
    }
    pq->size++;
}
bool QueueEmpty(Queue* pq)
{
    assert(pq);
    return pq->head == NULL;
}
int QueueSize(Queue* pq)
{
    assert(pq);
    return pq->size;
}
void QueuePop(Queue* pq)
{
    assert(pq);
    assert(!QueueEmpty(pq));
    if (pq->head == pq->patil)
    {
        free(pq->head);
        pq->head = pq->patil = NULL;
    }
    else
    {
        QueueNode* pcur = pq->head;
        pq->head = pq->head->next;
        free(pcur);
        pcur = NULL;
    }
    --pq->size;

}
int QueueFront(Queue* pq)
{
    assert(pq);
    assert(!QueueEmpty(pq));
    return pq->head->data;
}
int  QueueBack(Queue* pq)
{
    assert(pq);
    assert(!QueueEmpty(pq));
    return pq->patil->data;
}
void QueueDestory(Queue* pq)
{
    assert(pq);
    QueueNode* pcur = pq->head;
    while (pcur)
    {
        QueueNode* new = pcur->next;
        free(pcur);
        pcur = new;
    }
    pq->head = pq->patil = NULL;
    pq->size = 0;
}
typedef struct
{
    Queue q1;
    Queue q2;
} MyStack;
MyStack* myStackCreate()
{
    MyStack* pst = (MyStack*)malloc(sizeof(MyStack));
    if (pst == NULL)
    {
        perror("melloc fail");
        exit(1);
    }
    QueueInit(&pst->q1);
    QueueInit(&pst->q2);
    return pst;
}

void myStackPush(MyStack* obj, int x) {

    if (!QueueEmpty(&obj->q1))
    {
        QueuePush(&obj->q1, x);
    }
    else
    {
        QueuePush(&obj->q2, x);
    }

}

int myStackPop(MyStack* obj)
{
    Queue* Emp = &obj->q1;
    Queue* noneEmp = &obj->q2;
    if (QueueEmpty(&obj->q2))
    {
        noneEmp = &obj->q1;
        Emp = &obj->q2;
    }
    while (QueueSize(noneEmp) > 1)
    {
        QueuePush(Emp, QueueFront(noneEmp));
        QueuePop(noneEmp);
    }
    int top = QueueFront(noneEmp);
    QueuePop(noneEmp);
    return top;
}

int myStackTop(MyStack* obj)
{
    if (!QueueEmpty(&obj->q1))
    {
        return QueueBack(&obj->q1);
    }
    else
    {
        return QueueBack(&obj->q2);
    }

}

bool myStackEmpty(MyStack* obj) {
    return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2);

}

void myStackFree(MyStack* obj) {
    QueueDestory(&obj->q1);
    QueueDestory(&obj->q2);
    free(obj);
    obj = NULL;
}
int main()
{
    MyStack*C = myStackCreate();
    myStackPush(C, 3);
    myStackPop(C);
    myStackPush(C, 3);
    myStackPush(C, 3);
    myStackTop(C);
    myStackEmpty(C);
    myStackFree(C);
    return 0;
}